/*
 * @lc app=leetcode.cn id=343 lang=cpp
 *
 * [343] 整数拆分
 */

// @lc code=start
class Solution {
public:
    int integerBreak(int n) {
        //不可能拆分成大于等于5的数
        //4 = 2 * 2
        //拆分成2和3
        
        //8 = 3 * 3 * 2 (18)
        //8 = 2 * 2 * 2 * 2 (16)

        //尽量拆分成3

        if(n <= 3) return 1 * (n - 1);

        int ans = 1;
        while(n >= 5){
            n -= 3;
            ans *= 3;
        }
        ans *= n;

        return ans;
    }
};
// @lc code=end

